/**
 * Created With IntelliJ IDEA
 * Description:牛客网:BM53 缺失的第一个正整数
 * <a href="https://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5?tpId=295&tqId=2188893&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-27
 * Time: 22:15
 */

/**
 * 本题主要有两种较为简单的解法----哈希法和原地哈希法
 * 其中哈希法即先遍历一遍数组中的每一个元素,将每一个元素存入HashSet中,
 * 之后再从1到n+1一次检验HashSet是否存在这个元素,返回第一个不存在的即可.
 * 而原地哈希法是利用原数组的空间,设计一个合理的算法,做到再原数组上进行哈希,
 * 将空间复杂度由O(N)降到了O(1)
 * 因为哈希法较为简单,这里实现以下原地哈希法
 */
public class Solution {
    /**
     * 原地哈希法
     * 因为要利用原数组中的空间,而又不覆盖原来的值,所以就设计如下:
     * 1. 先处理负数和0,这里将负数和0的值全部归为n+1,防止影响后续操作
     * 2. 当nums[i]的绝对值小于n的时候,就将nums[i]-1对应的数组
     * 中的元素变为对应的负数.(这里设计成绝对值和将元素变为负数,
     * 都是为了做到遍历的时候,修改不覆盖原来的值,即我们改为负数
     * 后,将来遍历到这个元素的时候,仍然可以通过绝对值的方法找到
     * 其对应要修改的元素)
     * 3. 再从前往后遍历一遍原数组,输出第一个为整数的元素的下标+1,
     *    如果全为负数,则输出n+1
     */
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        //修改负数
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n+1;
            }
        }
        //哈希处理
        for (int i = 0; i < n; i++) {
            int temp = Math.abs(nums[i]);
            if (temp <= n) {
                nums[temp-1] = nums[temp-1]>0 ? -nums[temp-1] : nums[temp-1];
            }
        }
        //找到第一个非负数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }

}